Wireless broadband networks are being increasingly deployed in a multi-hop wireless mesh network (WMN) configuration. Currently, one application for WMNs is for extending or enhancing Internet connectivity for mobile clients located on the edge of the wired network (the so-called “last mile”). Commercial deployments of WMNs are currently underway in the United States. For example, in Medford, Oreg. and Chaska, Minn. mesh networks have been deployed (see, for example, www.chaska.net), and in Philadelphia, Pa. planning and development of a city-wide mesh network has been announced. One of the significant advantages to the deployment of mesh networks is the delivery of commercial Internet access to residents and local businesses.
In WMNs, the access points (or mesh routers) are rarely mobile and may not have power constraints. In addition these networks operate similarly to wired networks in having infrequent topology changes and limited node failures, for example. Although WMNs may be self-organizing, node additions and maintenance are still rare events. Also, since each mesh router may aggregate traffic flows for a large number of mobile clients, the aggregate traffic load of each mesh router changes infrequently. In IWMNs some mesh routers are also equipped with a gateway capability through which such routers interface with the wired network (see, for example, I. F. Akyildiz et al. “Wireless Mesh Networks: A Survey. Computer Network Journal (Elsevier), 2005, which is hereby incorporated by reference herein). In such networks traffic is mainly routed by the WMN wireless backbone between the mesh clients and the wired Internet and flows through the gateway nodes. One major problem facing such wireless networks is the capacity reduction due to interference among multiple simultaneous transmissions.
In wireless mesh networks, providing mesh routers with multiple-radios can greatly alleviate this problem in that using multiple-radios, nodes can transmit and receive simultaneously or can transmit on multiple channels simultaneously. However, due to the limited number of channels available, the interference cannot be completely eliminated and careful channel assignment must be done to mitigate the effects of interference. Indeed, several companies such as Mesh Dynamics Inc. (see, www.meshdynamics.com) have announced the availability of multi-radio mesh network products and solutions. In certain multi-radio applications, to make use of well-known IEEE 802.11-based radios, a channel is assigned to a radio interface for an extended period of time as long as traffic demand or network topology does not change.
The study of routing and channel assignments in wireless networks is an area of continued focus. For example, in A. Raniwala et al., “Centralized Channel Assignment and Routing Algorithms for Multi-channel Wireless Mesh Networks, ACM Mobile Computing and Communications Review, volume 8(2), pp. 50-65, 2004, which is hereby incorporated by reference herein, an observation was made that assigning channels and radios in a fixed order (i.e., assigning the first channel to the first radio, the second channel to the second radio and so on) will not lead to optimal achievable performance. Further, given that channel assignment and routing are inter-dependent the way in which such assignments are made will also have an impact on performance. This performance impact occurs because channel assignments have an impact on communications link bandwidths and the extent to which link transmissions interfere. This clearly impacts the routing used to satisfy traffic demands in a given network.
In the same way, traffic routing determines the traffic flows for each link thereby also have an affect on channel assignments. In particular, channel assignments need to be done in a way such that the communication requirements for the links can be satisfied. Heuristic approaches on channel assignments and load-aware routing have been proposed to improve the aggregate throughput of WMNs and balance load among gateways (see, e.g., Raniwala et al., supra., and A. Raniwala et al., “Architecture and Algorithms for an IEEE 802.11-based Multi-channel Wireless Mesh Network”, In Proc. IEEE INFOCOM, 2005, which is hereby incorporated by reference herein). In these approaches, an assumption is made that no system or hardware support is provided which allows for a radio interface to switch channels on a per-packet basis. A centralized joint channel assignment and multi-path algorithm is described in which the channel assignment algorithm considers high load edges first, and the routing algorithm uses both shortest path routing and randomized multi-path routing in an iterative fashion. However, these heuristic approaches will not result in optimal network performance. The system management software can compute the optimal channel assignment (using the aforementioned heuristic approaches) and, using such computed assignments apply routing and configurations to each elements periodically. However, routing protocols will still need to be executed to handle topology changes in the overall network.
However, despite the availability of certain routing and channel assignments it would be desirable to have a way to efficiently make joint channel and routing assignments in multi-radio WMNs that takes into account interference constraints, the number of channels in a network and the number of radio available at each mesh router, and which attempts to maximize the bandwidth allocated subject to fairness constraints.